package top.kiterunner.learning.data_structure.TrieTree;

/**
 * AdorynZhao in Tencent-UESTC.
 * Source Code Created on 2017/7/9.
 */
public class TrieTree {

    public final static int MAXSIZE = 26;

    public TrieTreeNode root;

    public TrieTree() {
        this.root = new TrieTreeNode();
    }

    // 字典树的插入
    public void insertNode(String str) {
        if (str == null || str.length() == 0) {
            return;
        }

        TrieTreeNode node = this.root;
        char[] chs = str.toCharArray();

        for (int i = 0; i < chs.length; i++) {
            int pos = chs[i] - 'a';
            if (node.child[pos] == null) {
                node.child[pos] = new TrieTreeNode();
            } else {
                node.child[pos].count++;
            }
            node.child[pos].ch = chs[i];
            node = node.child[pos];
        }
    }

    // 字典树的查找
    public int findCount(String str) {
        if (str == null || str.length() == 0) {
            return -1;
        }

        TrieTreeNode node = this.root;
        char[] chs = str.toCharArray();

        for (int i = 0; i < chs.length; i++) {
            int pos = chs[i] - 'a';
            if (node.child[pos] == null) {
                return 0;
            } else {
                node = node.child[pos];
            }
        }

        return node.count;
    }

    public class TrieTreeNode {
        public int count;
        public char ch;
        public TrieTreeNode[] child;

        public TrieTreeNode() {
            this.count = 1;
            this.child = new TrieTreeNode[MAXSIZE];
        }
    }
}
